package 算法.tanxin;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author lchenglong
 * @date 2022/3/4
 */
public class LRUCache {

    private Integer capacity;
    // 可以自定义一个双向链表 删除的移除的时候可以使时间复杂度为O(1)
    private LinkedList<Node> queue;
    private HashMap<Integer,Node> map;
    private Integer size = 0;

    public LRUCache(Integer capacity) {
        this.capacity = capacity;
        queue = new LinkedList<Node>();
        map = new HashMap<Integer, Node>(capacity);
    }

    public void put(Integer key,Integer value){
        Node node = map.get(key);
        if (size<=capacity){
            if (node == null){
                ++size;
                if (size>capacity) {
                    Node last = queue.removeLast();
                    map.remove(last.key);
                    --size;
                }
                node = new Node(key,value);
                queue.addFirst(node);
                map.put(key,node);
            } else {
                queue.remove(node);
                queue.addFirst(node);
            }
        }
    }

    public Integer get(Integer key){
        Node node = map.get(key);
        if (node == null){
            return -1;
        } else {
            queue.remove(node);
            queue.addFirst(node);
            return node.value;
        }
    }

    class Node{
        private Integer key;
        private Integer value;

        public Node(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache( 2 /* capacity */ );
        cache.put(1, 1);
        cache.put(2, 2);
        int value = cache.get(1); // returns 1
        cache.put(3, 3); // evicts key 2
        value = cache.get(2); // returns -1 (not found)
        cache.put(4, 4); // evicts key 1
        value = cache.get(1); // returns -1 (not found)
        value = cache.get(3); // returns 3
        value = cache.get(4); // returns 4
    }
}
